home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr49 / pgp23src.zip / RANDOM.C < prev    next >
C/C++ Source or Header  |  1993-05-18  |  26KB  |  787 lines
  1. /**********************************************************************
  2.     random.c - C source code for random number generation - 19 Nov 86
  3.     (c) Copyright 1986 by Philip Zimmermann.  All rights reserved.  
  4.  
  5.     Revised Jul 88 by PRZ and again Dec 88 by Allan Hoeltje
  6.         to use IBM PC 8253 timer0 for a faster counter.
  7.     Revised Apr 89 by PRZ to recycle random bytes.
  8.     Revised 29 Jul 91 by PRZ for use in more limited environments.
  9.     Later revised by several other folks to run in difficult environments
  10.     such as Unix, VAX/VMS and others.
  11.     Revised 2 Sep 92 by Peter Gutmann and PRZ to use MD5 to distill 
  12.     high quality randomness down from low-grade random noise.
  13.     Revised 25 Feb 93 by Colin Plumb to use MD5 much more for
  14.     more secure random numbers.  (randstir hacked)
  15.     Revised 4 Mar 93 by Colin Plumb to remove the CRUDE and non-USE_MD5
  16.     options, as no platform currently uses them, they make the code
  17.     hard to read, and they were suffering bit rot.  Also added
  18.     NO_ITIMER for the isc port and randaccum_later.
  19.  
  20.     This code generates truly random numbers derived from a counter that is 
  21.     incremented continuously while the keyboard is scanned for user input.
  22.     Every time the user touches a key, the least significant bits of the 
  23.     counter are pushed on a stack.  Later, this supply of random bytes can
  24.     be popped off the stack by applications requiring stochastic numbers.
  25.     Cryptographic applications require this kind of randomness.
  26.  
  27.     The only requirement to make this work is that keypress must be called 
  28.     frequently, and/or getkey must be called to read the keyboard.  
  29.  
  30.     Note that you can only get as many random bytes as the number of
  31.     bytes accumulated by the user touching the keyboard.
  32. **********************************************************************/
  33.  
  34. #ifdef UNIX
  35. #include <sys/types.h>
  36. #include <sys/time.h>
  37.  
  38. #if defined(linux)
  39. /* linux >= 0.99.9 has microsecond resolution gettimeofday() */
  40. #define    USE_GETTIMEOFDAY
  41. #endif
  42.  
  43. #ifdef NO_ITIMER    /* Some systems lie about itimer */
  44. #undef ITIMER_REAL
  45. #endif
  46.  
  47. #ifndef ITIMER_REAL
  48. #include <sys/times.h>
  49. #endif
  50. #endif /* UNIX */
  51.  
  52. #if defined(UNIX) || defined(VMS)
  53. #include <signal.h>
  54. #endif
  55.  
  56. #include    <stdio.h>    /* for putchar() and printf() */
  57. #include     <string.h>
  58. #ifndef _BSD
  59. #include     <time.h>
  60. #endif
  61. #include    "system.h"
  62. #include    "random.h"
  63. #include    "language.h"
  64.  
  65. static long pseudorand(void);    /* 31-bit LCG pseudorandom generator */
  66.  
  67. #ifdef  M_XENIX
  68. long time();
  69. #endif
  70. #ifdef UNIX
  71. #define    clock    Clock
  72. #endif
  73.  
  74. /*    pseudorand() is used mainly for debugging while porting to a new
  75.     machine-- it makes reproducible sequences, which makes debugging
  76.     easier.  To use it as the source of random numbers, define
  77.     PSEUDORANDOM.  Warning:  Don't do this for actual applications.
  78. */
  79. /**
  80.  ** Minimal Standard Pseudo-Random Number Generator
  81.  **
  82.  ** Author: Fuat C. Baran, Columbia University, 1988
  83.  **
  84.  ** Based on code in "Random Number Generators: Good Ones are Hard to Find",
  85.  ** by Stephen K. Park and Keith W. Miller in Communications of the ACM,
  86.  ** 31, 10 (Oct. 1988) pp. 1192-1201.
  87.  **
  88.  **/
  89.  
  90. /* some constants we need */
  91. #define A 16807L
  92. #define M 2147483647L        /* Mersenne prime 2^31 -1 */
  93. #define Q 127773L            /* M div A (M / A) */
  94. #define R 2836L                /* M mod A (M % A) */
  95.  
  96. static long pseudorand(void)
  97. {
  98.     long hi, lo;
  99. #ifdef DEBUG
  100.     static long seed = 1;
  101. #else
  102.     static long seed = 0;
  103. #endif
  104.     if (!seed || seed == M)
  105. #ifdef UNIX
  106.         seed = ((long) getpid() << 16) ^ time(NULL);
  107. #else
  108.         seed = ((long) clock() << 16) ^ time(NULL);
  109. #endif
  110.     hi = seed / Q;
  111.     lo = seed % Q;
  112.     if ((seed = A * lo - R * hi) <= 0)
  113.         seed += M;
  114.     return seed;
  115. }
  116.  
  117.  
  118. #ifndef PSEUDORANDOM        /* use truly random numbers */
  119.  
  120. /* #define USEPCTIMER */ /* use fast hardware timer on IBM PC or AT or clone */
  121. /* #define DEBUG */
  122.  
  123. /* Prototypes for kbhit() (whether the keyboard has been hit) and getch()
  124.    (like getchar() but no echo, no buffering).  Not available under some
  125.    implementations */
  126. #if defined(MSDOS) && !defined(__GO32__)
  127. #include <conio.h>
  128. typedef word16 fastcnt_t;
  129. #else
  130. typedef word32 fastcnt_t;
  131. #endif /* !MSDOS || __GO32__ */
  132.  
  133. #ifdef VMS
  134. int putch(int);
  135. #else
  136. #define    putch(c)    putc(c, stderr)
  137. #endif
  138.  
  139. #ifdef DEBUG
  140. #define DEBUGprintf1(x) fprintf(stderr,x)
  141. #define DEBUGprintf2(x,y) fprintf(stderr,x,y)
  142. #else
  143. #define DEBUGprintf1(x)
  144. #define DEBUGprintf2(x,y)
  145. #endif
  146.  
  147. #define POOLSIZE 256
  148. static int randcount = 0;        /* # of random bytes accumulated in pool */
  149. static byte randpool[POOLSIZE] = {0} ;    /* pool of truly random bytes */
  150. static int recyclecount = 0 ;    /* # of recycled random bytes accumulated */
  151. static byte recyclepool[POOLSIZE] = {0} ; /* pool of recycled random bytes */
  152.  
  153. static int accumpending = 0;    /* # of random bits to add to next request */
  154.  
  155. static void randstir(byte *pool);
  156.  
  157. /* fastcounter is a free-running counter incremented in main event loop. */
  158. static fastcnt_t fastcounter = 0;    /* not needed if we can use the PC timer. */
  159. static fastcnt_t lastcounter = 0;
  160. static int cbits;
  161. static char toofast = 0;
  162. /* toofast indicates keystroke rejected because it was typed too fast */
  163.  
  164. #ifdef AMIGA
  165. int aecho;
  166. #endif
  167.  
  168. /* Information needed by the MD5 code for distilling large quantities of
  169.    semi-random information into a small amount of highly-random information.
  170.    This works as follows:
  171.  
  172.    Initially we have no random information.  Whenever we add more slightly
  173.    random data, we put it in the MD5 data field and run MD5 over the
  174.    random byte pool.  This propagates the randomness in the data evenly
  175.    throughout the pool due to the avalanche effect of the MD5 transformation.
  176.    The randomness transformation is carried out inside capturecounter() when
  177.    the data is entered, and is transparent to the operation of the rest of
  178.    the code.
  179. */
  180.  
  181. #include "md5.h"
  182. static byte seedBuffer[ 64 ];            /* Buffer for MD5 seed value */
  183. static boolean isInitialised = FALSE;    /* Whether buffer has been inited */
  184. static byte iv[ 16 ];                    /* IV for MD5 transformation */
  185.  
  186. #ifdef USEPCTIMER    /* we will use fast hardware timer on IBM PC */
  187. /* #include <conio.h> */    /* function definitions for inp() and outp() */
  188. /* outp() and inp() works only for Microsoft C for IBM PC or AT */
  189. /* timer0 on 8253-5 on IBM PC or AT tics every .84 usec. */
  190. #define timer0        0x40    /* 8253 timer 0 port */
  191. #define timercntl    0x43    /* 8253 control register */
  192. #define timer0rwl    0x00    /* read lo/hi bytes of cntr 2 with latch */
  193. #define timer0rnl    0x30    /* read lo/hi bytes of cntr 2 w/o latch */
  194.  
  195. static byte latched_hitimer = 0; /* captured by keyboard ISR */
  196. static byte latched_lotimer = 0; /* captured by keyboard ISR */
  197. /* when kbisr captures timer, timer_latched is set. */
  198. static boolean timer_latched = FALSE;
  199.  
  200. static void kbisr(void)    /* Keyboard Interrupt Service Routine (ISR) */
  201. /*
  202.     kbisr should be called on the way into, or on the way out of,
  203.     or from within the DOS keyboard ISR, as long as it gets called
  204.     at the time of a keyboard interrupt.  Assumes that the real
  205.     DOS keyboard ISR captures the keystroke in the normal way.
  206.     Only the hardware timer counter is captured by the kbisr routine,
  207.     leaving the actual keystroke capture to the normal DOS keyboard ISR.
  208.     We indicate that a timer capture has taken place by setting 
  209.     timer_latched.
  210.  
  211.     NOTE: WE STILL NEED TO FIND A WAY to connect this subroutine with the 
  212.     normal keyboard ISR, so that kbisr gets called when there's a keyboard
  213.     interrupt.
  214. */
  215. {    outp(timercntl,timer0rwl);
  216.     latched_lotimer = inp(timer0);
  217.     latched_hitimer = inp(timer0);
  218.     timer_latched = TRUE;
  219. }    /* kbisr */
  220.  
  221. static unsigned short pctimer0(void)
  222. {
  223. /*    Reads and returns the hardware 8253 timer0 on the PC or AT
  224. **    or clone, shifted right 1 bit.
  225. **
  226. **    DO NOT SET THE HARDWARE COUNTER TO ZERO. It is already initialized
  227. **    by the system to be used by the clock.  It is set up in mode 3
  228. **    (square wave rate generator) and counts down by 2 from 0 (0xFFFF+1)
  229. **    to produce an 18.2 Hz square wave.  We may, however, READ the
  230. **    lo and hi bytes without causing any problems.  BUT just
  231. **    remember that the lo byte will always be even (since it is
  232. **    counting by two).
  233. **
  234. **    Note that we can not use counter 1 since it is tied to the
  235. **    dynamic RAM refresh hardware.  Counter 2 is tied to the 8255
  236. **    PPI chip to do things like sound.  Though it would be safe to
  237. **    use counter 2 it is not desirable since we would have to turn
  238. **    the speaker on in order to make the timer count!  Normally one
  239. **    sets counter 2 to mode 3 (square wave generator) to sound the
  240. **    speaker.  You can set mode 2 (pulse generator) and the speaker
  241. **    hardly makes any sound at all, a click when you turn it on and
  242. **    a click when you turn it off.  Counter 0 should be safe if
  243. **    we only read the counter bytes.
  244. **
  245. **    WARNING:  To use the hardware timer the way it really should be
  246. **    used, we ought to capture it via a keyboard interrupt service
  247. **    routine (ISR).    Otherwise, we may experience weaknesses in randomness
  248. **    due to harmonic relationships between the hardware counter frequency
  249. **    and the keyboard software polling frequency.  Unfortunately, this
  250. **    implementation does not currently use keyboard interrupts to
  251. **    capture the counter.  This is not a problem if we don't use the
  252. **    hardware counter, but instead use the software counter fastcounter.
  253. **    Thus, the hardware counter should not be used at all, unless we
  254. **    support it with an ISR.
  255. */
  256.     unsigned short t ;
  257.     /* See if timer has been latched by kbisr(). */
  258.     if (!timer_latched) /* The timer was not already latched. */
  259.         kbisr();    /* latch timer */
  260.     /* return latched timer and clear latch */
  261.     t = (     (((unsigned short) latched_hitimer) << 8) |
  262.          ((unsigned short) latched_lotimer)
  263.         ) >> 1 ;
  264.     timer_latched = FALSE;
  265.     return (t) ;
  266. }    /* pctimer0 */
  267.  
  268. #endif    /* ifdef USEPCTIMER */
  269.  
  270.  
  271. /* keybuf is used only by keypress(), getkey(), and capturecounter(). */
  272. static short keybuf = 0;
  273.  
  274.  
  275. #ifdef VMS
  276.  
  277. extern unsigned long    vms_clock_bits[2];    /* VMS Hardware Clock */
  278. extern const long    vms_ticks_per_update;    /* Clock update int. */
  279.  
  280. #endif /* VMS */
  281.  
  282. static void capturecounter(void)
  283. /*    Push a fast counter on the random stack.  Should be called when
  284. **    the user touches a key or clicks the mouse.
  285. */
  286. {
  287.     fastcnt_t dt;
  288. #ifndef MSDOS
  289.     byte *random_xtra;    /* extra timer info */
  290. #endif
  291.     static byte abits = 0;    /* number of accumulated bits in accum */
  292.     unsigned int accum1;
  293.  
  294. #define cbitsmask ((1 << cbits)-1)
  295.  
  296.     /*    fastcounter only contains timing information, in the form of a 
  297.         free-running timer, either hardware or software.
  298.         accum1 contains stuff from fastcounter and other sources,
  299.         like the actual key the user hit.
  300.     */
  301.  
  302. #if defined(USEPCTIMER) /* we will use fast hardware timer on IBM PC */
  303.     fastcounter = pctimer0();    /* capture hardware timer */
  304. #endif    /* not USEPCTIMER */
  305.  
  306. #ifdef VMS
  307. #define    HW_TIMER    1        /* using hardware timer */
  308.     /* Capture fast system timer: */
  309.     SYS$GETTIM(vms_clock_bits);
  310. #ifdef TEST_COUNTER
  311.     fprintf(stderr," time %10ol %10ol\n",vms_clock_bits[0],vms_clock_bits[1]);
  312. #endif
  313.     /* vms_clock_bits[0] and vms_ticks_per_update are 32-bits each. */
  314.     fastcounter = vms_clock_bits[0] / vms_ticks_per_update;
  315. #endif /* VMS */
  316.  
  317. #ifdef UNIX
  318. #define    HW_TIMER    1        /* using hardware timer */
  319. #ifdef USE_GETTIMEOFDAY
  320.     {    static struct timeval tv;
  321.         gettimeofday(&tv, NULL);
  322.         /* divide by 64 (we can at least expect a 60Hz clock) */
  323.         fastcounter = tv.tv_usec / (1000000/64) + tv.tv_sec * 64;
  324.         random_xtra = (byte *) &tv;
  325. #define    XTRA_BYTES    (sizeof(struct timeval))
  326.     }
  327. #else /* !USE_GETTIMEOFDAY */
  328. #ifdef ITIMER_REAL
  329.     {    static struct itimerval it;
  330.         getitimer(ITIMER_REAL, &it);
  331.         if (it.it_value.tv_sec == 0 && it.it_value.tv_usec == 0)
  332.         {    /* start the timer */
  333.             it.it_value.tv_sec = 100000;
  334.             it.it_value.tv_usec = 0;
  335.             it.it_interval.tv_sec = 100000;
  336.             it.it_interval.tv_usec = 0;
  337.             signal(SIGALRM, SIG_IGN);    /* just in case.. */
  338.             setitimer(ITIMER_REAL, &it, NULL);
  339.             return;
  340.         }
  341.         /* divide by 64 (we can at least expect a 60Hz clock) */
  342.         fastcounter = 6400000-(it.it_value.tv_usec / (1000000/64)
  343.                 + it.it_value.tv_sec * 64);
  344.         random_xtra = (byte *) &it.it_value;
  345. #define    XTRA_BYTES    (sizeof(struct timeval))
  346.     }
  347. #else /* !ITIMER_REAL */
  348.     {    static struct tms tms;
  349.         fastcounter = times(&tms);
  350.         random_xtra = (byte *) &tms;
  351. #define    XTRA_BYTES    (sizeof(struct tms))
  352.     }
  353. #endif /* !ITIMER_REAL */
  354. #endif /* !USE_GETTIMEOFDAY */
  355. #endif /* UNIX */
  356.  
  357.     dt = fastcounter - lastcounter;
  358. #ifdef TEST_COUNTER
  359.     fprintf(stderr,"%6lu", dt);
  360. #endif
  361. #ifndef NO_CBIT_STRIP
  362.     dt /= 6;    /* use 2.5 bits less than the actual count */
  363. #endif
  364.     for (cbits = 0; dt; ++cbits)
  365.         dt >>= 1;
  366. #if 0    /* I don't think this is necessary - CP */
  367.     if (cbits > 8)
  368.         cbits = 8;
  369. #endif
  370.  
  371. #ifdef TEST_COUNTER
  372.     fprintf(stderr,"%6u\n", cbits);
  373. #endif
  374.     if (cbits <= 0)
  375.     {
  376.         toofast++;    /* indicate a too-fast keystroke */
  377.         return;    /* only captures if enough time has passed */
  378.     }
  379.  
  380.     lastcounter = fastcounter;    /* latch timer info */
  381.  
  382.     /* Initialise the MD5 info if necessary */
  383.     if( !isInitialised )    /* we probably shouldn't bother */
  384.     {    memset(seedBuffer, 0, 64);
  385.         memset(iv, 0, 16);
  386.         isInitialised = TRUE;
  387.     }
  388.  
  389.     /*    Add the slightly-random data to the MD5 input buffer.  Currently we
  390.         just add a few bytes of environmental noise, but we could mix in 
  391.         up to 512 bits worth.  This should be extended in a system-specific
  392.         manner.
  393.     */
  394.     seedBuffer[ 0 ] = keybuf;    /* actual character user typed */
  395.     seedBuffer[ 1 ] = lastcounter & 0xFF;
  396.     seedBuffer[ 2 ] = lastcounter >> 8;
  397. #ifdef MSDOS
  398.     accum1 = ( int ) clock();            /* clock ticks */
  399.     seedBuffer[ 3 ] = accum1 & 0xFF;
  400.     seedBuffer[ 4 ] = accum1 >> 8;
  401. #endif
  402. #ifndef USE_GETTIMEOFDAY
  403.     accum1 = ( int ) time(NULL);        /* seconds */
  404.     seedBuffer[ 5 ] = accum1 & 0xFF;
  405.     seedBuffer[ 6 ] = accum1 >> 8;
  406. #endif /* !USE_GETTIMEOFDAY */
  407. #ifdef XTRA_BYTES    /* add some extra "random" stuff */
  408.     memcpy(seedBuffer+16, random_xtra, XTRA_BYTES);
  409. #endif
  410.     /* The preceding "noise quantum" has only cbits worth of randomness. */
  411.     /* Spread it uniformly across the entire pool */
  412.  
  413.     randstir(randpool);
  414.  
  415.     /*
  416.         Now the somewhat dubious bit:  In order to make this fit in with
  417.         the existing code, we use the existing mechanism of keeping track
  418.         of a high-water mark in the buffer.  This is actually reasonably
  419.         realistic, since it keeps a count of what percentage of the full
  420.         buffer is random enough-- measuring the "molarity" of solution. 
  421.     */
  422.  
  423.     abits += cbits;        /* Update count of bits of randomness */
  424.     while (abits >= 8)
  425.     {    /* We've got another byte's worth, increment the buffer pointer */
  426.         if (randcount < sizeof(randpool))
  427.             randcount++; /* not a byte counter-- now a molarity of randomness */
  428.         abits -= 8;
  429.     }
  430. }    /* capturecounter */
  431.  
  432.  
  433. /* Because these truly random bytes are so unwieldy to accumulate,
  434.    they can be regarded as a precious resource.  Unfortunately,
  435.    cryptographic key generation algorithms may require a great many
  436.    random bytes while searching about for large random prime numbers.
  437.    Fortunately, they need not all be truly random.  We only need as
  438.    many truly random bytes as there are bytes in the large prime we
  439.    are searching for.  These random bytes can be recycled and modified
  440.    via pseudorandom numbers until the key is generated, without losing
  441.    any of the integrity of randomness of the final key.
  442. */
  443.  
  444.  
  445. static void randstir(byte *pool)
  446. /* Stir up the recycled random number bin, via a pseudorandom generator
  447.    Any truly random bytes stored into the seedBuffer are hashed into the
  448.    pool, and then destroyed for security reasons. */
  449. {    int i;
  450.     int j;
  451.     /* Now use MD5 to diffuse the randomness in these bits over the random
  452.        byte pool, raising the salinity of randomness in the pool.  The
  453.        transformation is carried out by "encrypting" the data in CFB mode
  454.        with MD5 as the block cipher */
  455.     for(i = 0; i < POOLSIZE; i += 16)
  456.     {
  457.         Transform((UINT4 *) iv, (UINT4 *) seedBuffer);
  458.         for(j = 0; j < 16; j++)
  459.             pool[i+j] ^= iv[j];
  460.         memcpy(iv, pool+i, 16);
  461.     }
  462. /* CFB encryption is reversible; if we want the stirring operation to
  463.    be strictly one-way, we must destroy the key.  The operation
  464.    accomplishes that, and increases the end-to-beginning feedback
  465.    in randstir(), in an attempt to make all bytes depend on all
  466.    other bytes. */
  467.     memcpy(seedBuffer, pool+POOLSIZE-sizeof(seedBuffer),
  468.            sizeof(seedBuffer));
  469. }    /* randstir */
  470.  
  471.  
  472. short randload(short bitcount)
  473. /*    Flushes stale recycled random bits and copies a fresh supply of raw 
  474.     random bits from randpool to recyclepool.  Returns actual number of 
  475.     bits transferred. */
  476. {    int bytecount;
  477.     bytecount = (bitcount+7)/8;
  478.     bytecount = min(bytecount,randcount);
  479.     randflush();    /* reset recyclecount, discarding recyclepool */
  480.     while (bytecount--)
  481.         recyclepool[recyclecount++] = randpool[--randcount];
  482.     DEBUGprintf2("\nAllocating %d recycleable random bytes. ",recyclecount);
  483.     randstir(recyclepool);
  484.     recyclecount = sizeof(recyclepool);
  485.     return(recyclecount*8);
  486. }    /* randload */
  487.  
  488.  
  489. void randflush(void)    /* destroys pool of recycled random numbers */
  490. /* Ensures no sensitive data remains in memory that can be recovered later. */
  491. {    
  492. /* We do not actually destroy the random bytes (which would be somewhat
  493.    wasteful); we just stir them so that they are irretrievable.  This
  494.    assumes that MD5 is truly one-way. */
  495.     randstir(recyclepool);
  496.     recyclecount = 0;
  497. }    /* randflush */
  498.  
  499. short try_randombyte(void)
  500. /* Returns a truly random byte if any are available, or -1 if none.
  501.  * it is not an error to call this if none are available.  For example,
  502.  * make_random_ideakey calls it to add to its other sources of pseudo-random
  503.  * noise.
  504.  */
  505. {
  506.     /* First try to get a cheap recycled random byte, if there are any. */
  507.     if (recyclecount)    /* nonempty recycled pool */
  508.     {
  509.         byte b;
  510.         b = recyclepool[--recyclecount];
  511.         if (!recyclecount)    /* Used them all up? */
  512.             randstir(recyclepool);    /* Refresh recycled pool */
  513.         return b;
  514.     }
  515.  
  516.     /* Empty recycled pool.  Try a more expensive fresh random byte. */
  517.  
  518.     if (randcount)    /* nonempty random pool--return a very random number */
  519.         return (randpool[--randcount]);
  520.  
  521.     /* No, all is for naught.  Return -1. */
  522.     return -1;
  523. }
  524.  
  525. short randombyte(void)
  526. /*    Returns truly random byte from pool, or a pseudorandom value
  527. **    if pool is empty.  It is recommended that the caller check
  528. **    the value of randcount before calling randombyte.
  529. */
  530. {    
  531.     short r;
  532.  
  533.     r = try_randombyte();
  534.     if (r >= 0)
  535.         return r;
  536.  
  537.     /* Oops!  Random pool empty.  Were there some unsatisifed deferred
  538.        accumulation requests? */
  539.     randaccum(0);
  540.     r = try_randombyte();
  541.     if (r >= 0)
  542.         return r;
  543.     
  544.     /* Alas, fresh random pool is truly empty.  Complain, and return
  545.        a pseudorandom byte.  Pseudorandom numbers are bad for
  546.        cryptographic applications.  Although we will return a
  547.        pseudorandom byte in the low order byte, indicate error by
  548.        making the result negative in the high byte.
  549.     */
  550.     fprintf(stderr, " \007WARNING: Random pool empty! ");
  551.     return ( (pseudorand() & 0xFF) ^ (-1) );
  552. }    /* randombyte */
  553.  
  554.  
  555. static boolean keypress(void)    /* TRUE iff keyboard input ready */
  556. {    /* Accumulates random numbers by timing user keystrokes. */
  557.     static short lastkey = 0; /* used to detect autorepeat key sequences */
  558.     static short next_to_lastkey = 0; /* allows a single repeated key */
  559.  
  560. #ifndef HW_TIMER    /* no fast hardware timer available */
  561.     fastcounter++;    /* used in lieu of fast hardware timer counter */
  562. #endif    /* ifndef HW_TIMER */
  563.  
  564.     if (keybuf & 0x100)    /* bit 8 means keybuf contains valid data */
  565.         return( TRUE );    /* key was hit the last time thru */
  566.  
  567.     /*
  568.      * If HW_TIMER is defined we don't need a busy loop, so keypress
  569.      * waits for a key and will always return TRUE.
  570.      */
  571. #ifndef HW_TIMER
  572.     if (kbhit() == 0)    /* keyboard was not hit */
  573.         return( FALSE );
  574. #endif
  575.  
  576.     keybuf = getch() | 0x100; /* set data latch bit */
  577.  
  578.     /* Keyboard was hit.  Decide whether to call capturecounter... */
  579.  
  580.     /*  Guard against typahead buffer defeating fastcounter's randomness.
  581.     **  This could be a problem for multicharacter sequences generated
  582.     **  by a function key expansion or by the user generating keystrokes
  583.     **  faster than our event loop can handle them.  Only the last
  584.     **  character of a multicharacter sequence will trigger the counter
  585.     **  capture.  Also, don't let the keyboard's autorepeat feature
  586.     **  produce nonrandom counter capture.  However, we do allow a 
  587.     **  single repeated character to trigger counter capture, because
  588.     **  many english words have double letter combinations, and it's 
  589.     **  unlikely a typist would exploit the autorepeat feature to
  590.     **  type a simple double letter sequence.
  591.     **  We have some separate checks in capturecounter() to guard
  592.     **  against other reasons for characters coming in too fast.
  593.     */
  594.  
  595. #ifndef HW_TIMER
  596.     if (kbhit() == 0)    /* nothing in typahead buffer */
  597. #endif
  598.     {    /* don't capture counter if key repeated */
  599.         if (keybuf != lastkey)
  600.             capturecounter(); /* read random noise from environment */
  601.         else if (keybuf != next_to_lastkey) /* allow single repeat */
  602.             capturecounter();
  603.         next_to_lastkey = lastkey;
  604.         lastkey = keybuf;
  605.     }
  606.     return( TRUE );
  607. }    /* keypress */
  608.  
  609.  
  610. static short getkey(void)    /* Returns data from keyboard (no echo). */
  611. {    /* Also accumulates random numbers via keypress(). */
  612.     while(! keypress() )        /* loop until key is pressed. */
  613.         ;
  614.     return( keybuf &= 0xff);    /* clear latch bit 8 */
  615. }    /* getkey */
  616.  
  617.  
  618. #define BS    8        /* ASCII backspace */
  619. #define CR    13        /* ASCII carriage return */
  620. #define LF    10        /* ASCII linefeed */
  621. #define DEL 0177    /* ASCII delete */
  622.  
  623. /* Since getting random bits from the keyboard requires user attention,
  624.    we buffer up requests for them until we can do one big request. */
  625.  
  626. void randaccum_later(short bitcount)
  627. {
  628.     accumpending += bitcount;    /* Wow, that was easy! :-) */
  629. }
  630.  
  631. /* We will need a series of truly random bits for key generation.
  632.    In most implementations, our random number supply is derived from
  633.    random keyboard delays rather than a hardware random number
  634.    chip.  So we will have to ensure we have a large enough pool of
  635.    accumulated random numbers from the keyboard.  Later, randombyte
  636.    will return bytes one at a time from the accumulated pool of
  637.    random numbers.  For ergonomic reasons, we may want to prefill
  638.    this random pool all at once initially.  The randaccum function
  639.    prefills a pool of random bits.
  640. */
  641.  
  642. void randaccum(short bitcount)    /* Get this many random bits ready */
  643. {    short nbytes;
  644. #ifndef HW_TIMER
  645.     unsigned long timer;
  646. #endif
  647.     int fasts_rejected = 0;            /* number of too-fast keystrokes */
  648.  
  649.     bitcount += accumpending;    /* Do deferred accumulation now */
  650.     accumpending = 0;
  651.     nbytes = min((bitcount+7)/8,sizeof(randpool));
  652.     fasts_rejected = 0;    /* number of too-fast keystrokes */
  653.     toofast = 0;    /* clear too-fast latch */
  654.  
  655.     if (randcount < nbytes)    /* if we don't have enough already */
  656.     {    fprintf(stderr,
  657. PSTR("\nWe need to generate %d random bytes.  This is done by measuring the\
  658. \ntime intervals between your keystrokes.  Please enter some random text\
  659. \non your keyboard until you hear the beep:\n"), nbytes-randcount);
  660. #ifdef NEEDBREAK
  661.         ttycbreak();
  662. #endif
  663.         /* display counter to show progress */
  664.  
  665.         while (randcount < nbytes)
  666.         {
  667. #ifndef TEST_COUNTER
  668.             fprintf(stderr,"\r%3d ",nbytes-randcount);
  669. #endif
  670.             fflush(stderr);
  671.             getkey();
  672.             if (toofast)
  673.             {    fasts_rejected++;    /* keep score */
  674.                 toofast = 0;        /* reset latch */
  675.                 putc('?', stderr);    /* indicate trouble */
  676.             }
  677.             else 
  678.                 putc('.', stderr);
  679.         }
  680.  
  681.         fprintf(stderr,PSTR("\007*\n-Enough, thank you.\n"));
  682.  
  683.         if (fasts_rejected > 2)    /* Did user type too fast? */
  684.             fprintf(stderr,PSTR("(Ignored %d keystrokes that were typed too fast.)\n"), 
  685.                 fasts_rejected);
  686.  
  687. #ifdef HW_TIMER    /* keypress() would block if using hardware timer */
  688.         sleep(1);
  689. #else
  690.         /* Clean up typeahead for at least 1 full second... */
  691.         timer = time(NULL) + 1;    /* need at least 1 second of quiet */
  692.         while ((unsigned long) time(NULL) <= timer)
  693.         {    if (keypress())    /* user touched a key, reset timer */
  694.             {    getkey();
  695.                 timer = time(NULL) + 1;
  696.             }
  697.         }
  698. #endif
  699.  
  700. #ifdef NEEDBREAK
  701.         ttynorm();
  702. #endif /* !NEEDBREAK */
  703.     }
  704. }    /* randaccum */
  705.  
  706.  
  707. int getstring(char *strbuf, int maxlen, boolean echo)
  708. /*    Gets string from user, with no control characters allowed.
  709.     Also accumulates random numbers by calling getkey().
  710.     maxlen is max length allowed for string.
  711.     echo is TRUE iff we should echo keyboard to screen.
  712.     Returns null-terminated string in strbuf.
  713. */
  714. {    short i;
  715.     char c;
  716. #ifdef NEEDBREAK
  717.     ttycbreak();
  718. #endif
  719. #ifdef AMIGA
  720.     aecho = (int)echo;
  721.     echo = FALSE;   /* echo is done in getch */
  722. #endif  /* AMIGA */
  723.     fflush(stdout);
  724.     i=0;
  725.     while (TRUE)
  726.     {    
  727. #ifndef VMS
  728.         fflush(stderr);
  729. #endif /* VMS */
  730.         c = getkey();
  731. #ifdef VMS
  732.         if (c == 25) {  /*  Control-Y detected */
  733.             ttynorm();
  734.             breakHandler(SIGINT);
  735.         }
  736. #endif /* VMS */
  737.         if (c==BS || c==DEL)
  738.         {    if (i)
  739.             {    if (echo)
  740.                 {    putch(BS);
  741.                     putch(' ');
  742.                     putch(BS);
  743.                 }
  744.                 i--;
  745.             }
  746.             continue;
  747.         }
  748.         if (c < ' ' && c != LF && c != CR)
  749.         {    putch('\007');
  750.             continue;
  751.         }
  752.         if (echo) putch(c);
  753.         if (c==CR)
  754.         {    if (echo) putch(LF);
  755.             break;
  756.         }
  757.         if (c==LF)
  758.             break;
  759.         if (c=='\n')
  760.             break;
  761.         strbuf[i++] = c;
  762.         if (i>=maxlen)
  763.         {    fprintf(stderr,"\007*\n");    /* -Enough! */
  764.             while (keypress())
  765.                 getkey();    /* clean up any typeahead */
  766.             break;
  767.         }
  768.     }
  769.     strbuf[i] = '\0';    /* null termination of string */
  770. #ifdef NEEDBREAK
  771.     ttynorm();
  772. #endif
  773.     return(i);        /* returns string length */
  774. }    /* getstring */
  775.  
  776.  
  777. #endif            /* ifndef PSEUDORANDOM */
  778.  
  779. void flush_input(void)
  780. {    /* on unix ttycbreak() will flush the input queue */
  781. #ifndef HW_TIMER
  782.     while (keypress())    /* flush typahead buffer */
  783.         getkey();
  784. #endif
  785. }
  786.  
  787.